package sort.insert;

import sort.SortArr;

import java.util.Arrays;

/**
 * @ Project: JavaSort
 * @ Package: sort.insert
 * @ Title 标题（要求能简洁地表达出类的功能和职责）
 * @ Description: 描述（简要描述类的职责、实现方式、使用注意事项等）
 * @ author : qw
 * @ CreateDate: 2020/12/21 14:32
 * @ Version: 1.0
 * @ Copyright: Copyright (c) 2020
 * @ History: 修订历史（历次修订内容、修订人、修订时间等）
 */
public class BinaryInsertSort {

    public static void binaryInsertSort() {
        int[] arr = Arrays.copyOf(SortArr.sortArr,SortArr.sortArr.length);
        System.out.println("二分法插入排序前的数组");
        System.out.println(Arrays.toString(arr));
        for (int i=0; i< arr.length;i++) {
            int temp = arr[i];
            int left = 0;
            int right = i - 1;
            int mid = 0;
            while (left <= right) {
                mid = (left + right) / 2;
                if (temp < arr[mid]) {
                    right = mid - 1;
                }else {
                    left = mid + 1;
                }
            }
            for (int j = i - 1;j >= left;j--) {
                arr[j+1] = arr[j];
            }
            if (left != i) {
                arr[left] = temp;
            }
        }
        System.out.println("二分法插入排序后的数组");
        System.out.println(Arrays.toString(arr));
    }
}
